This application claims the benefit of Taiwanese application Serial No. 89111196, filed on Jun. 8, 2000.
1. Field of the Invention
The present invention relates to a method for scheduling execution sequence. More particularly, the present invention relates to a method for scheduling execution sequence of read/write operation suitable for a computer system.
2. Description of the Related Art
There are two major operations for a central process unit (CPU) to access a dynamic random access memory (DRAM): one is the read operation and the other is the write operation. Different operational characteristics exist between the read and write operations for the CPU, and therefore if we can aptly arrange the read and write operations, it can be executed faster and with more efficiency.
FIG. 1 shows a block diagram of a part of a computer system. Referring to FIG. 1, when the CPU 102 intends to write data into or read data from the DRAM 104, the CPU pushes a write request W or read request R into a write queue 108 or a read queue 110 respectively within a control unit 106. After it is processed by the control unit 106, the write request W or the read request R is popped from the write queue 108 or the read queue 110 respectively. While the write request W or the read request R is popped, the write or read operation is executed and controlled by a DRAM bus state machine 112 in the control unit 106. For example, if there are three data to be written or read, three corresponding write requests WA, WB, and WC or three corresponding read requests RA, RB, and RC are asserted. Then, the write operation includes write commands WCMD_A, WCMD_B, and WCMD_C, and the corresponding written data WDATA_A, WDATA_B and WDATA_C. If the read requests are asserted, the read operation includes read commands RCMD_A, RCMD_B, and RCMD_C, and the corresponding read data RDATA_A, RDATA_B, and RDATA_C. The DRAM bus state machine 112 detects the status of the DRAM bus for transmitting the write command WCMD, written data WDATA, or read command RCMD to the DRAM 104, and the DRAM 104 sends read data RDATA.
FIG. 2 is a timing chart for illustrating the CPU performing read/write operations to the DRAM according to the conventional method. Referring to FIG. 2, the conventional method is performed according to a sequence queuing the write and read requests. The read queue signal R_Queue shows a timing relation that read requests RA, RB, and RC are respectively pushed into the read queue 110, and the write queue signal W_Queue shows a timing relation that write requests WA, and WB are respectively pushed into the write queue 108. The pop signal POP represents a time sequence that the write requests WA, and WB queued in the write queue 108 and read requests RA, RB, and RC queued in the read queue 110 are popped. For example, according to a time sequence that the write requests and the read requests are sequentially and respectively queued in the write queue 108 and the read queue 110, the read requests RA, RB, the write requests WA, WB, and the read request RC are sequentially popped. Signal CLK is the system clock, and the read commands RCMD_A, RCMD_B the write commands WCMD_A WCMD_B, and the read command RCMD_C are sequentially asserted on the command signal line CMD. As the data line DATA detects the commands RCMD_A, RCMD_B WCMD_A, WCMD_B, and RCMD_C, the corresponding data RDATA_A, RDATA_B WDATA_A WDATA_B and RDATA_C are transmitted on the data line DATA.
Among these bus signals, the write command WCMD, the write data WDATA and the read command RCMD are transmitted from the CPU 102 to the DRAM 104 and thus they are called down signals, while the read data RDATA is transmitted from the DRAM 104 to the CPU 102, which is called an up signal. Therefore, there must exist a turn around cycle, such as time interval t1 or t2 shown in FIG. 2, between the up and down signals because the DRAM bus has to change its transmission direction. If the turn around cycle can be reduced, data transmission rate can be increased.
Furthermore, the CPU 102 sometimes needs to read related data for executing a program because the read operation depends on the program. However, with respect to the DRAM 104, the dependence between the write operation and an executed program is not as related as the read operation. Therefore, the read operation is more important and necessary than the write operation for the CPU 102, and so the priority of the read operation is higher than that of the write operation, for which the read operation will be performed in advance to benefit the CPU""s task.
As mentioned above, the conventional method utilizes a method termed read around write (RAW) to perform the read operation first. Generally there are many RAW methods used, and read around pre write (RAPW) is used as an example to explain the conventional method. FIG. 3 is a timing diagram for illustrating the read and write operations using the RAPW method. As shown in FIG. 3, from the read queue signal R_Queue and the write queue signal W_Queue, the read and write requests are pushed into the read queue 110 and the write queue 108 respectively in a sequence of read requests RA, RB, write requests WA, WB, and read request RC. According to the conventional RAPW method, the read operation can run around a write operation ahead of the read operation and be performed first. As shown in FIG. 3, the pop sequence accordingly becomes read requests RA, RB, write request WA, read request RA and write request WB. While read requests RA and RB are sequentially popped, read commands RCMD_A and RCMD_B are asserted on the command signal line CMD. Processed by the DRAM 104, the corresponding read data RDATA_A and RDATA_B are sent out through the data signal line DATA, in which if each read data contains four data, it needs four cycles to complete each read operation as shown in FIG. 3. Afterwards, the write command WCMD_A and write data WDATA_A are sent to the DRAM 104 through the command signal line CMD and the data signal line DATA respectively. A turn around cycle, namely the time interval t1, exists between the read data RDATA_B and the write data WDATA_A. Similarly, the read command RCMD_C is asserted on the command signal line CMD and then the read data is sent out of the DRAM 104. Then, the write command WCMD_B and write data WDATA_B are sent to the DRAM 104 through the command signal line CMD and the data signal line DATA respectively. As shown in FIG. 3, it requires three turn around cycles, the time intervals t1, t2 and t3, for performing the read and write operations by the RAPW method.
As discussed above, in the RAPW method, the read operation can only run around one write operation ahead it, and therefore, at the most the write queue 108 can reserve one write command WCMD therein. After the write request WB is pushed into the write queue 108, the write request WA can be popped. The DRAM bus status machine 112 sends the write command WCMD_A, depending on the status of the DRAM bus. The read request RC is pushed into the read queue 110 after the write request WB, but the read request RC must be popped before the write request WB according to the RAPW method. Namely, the read command RCMD_C has to be sent before the write command WCMD_B. As a result, after the write data WDATA_A is sent to the DRAM 104 through the data signal line DATA, the read data RDATA_C is sent out of the DRAM 104 and the write data WDATA_B is sent to the DRAM 104 in turn. Therefore, three turn around cycles occur, decreasing the data transmission rate.
Furthermore, according to the RAPW method, the read request RC has to be popped first before the write request WB. However, if addresses corresponding to the read request RC and the write request WB are the same, address hit occurs, causing a wrong result for the read data RDATA_C. Because both addresses are the same, actually the write command WCMD_B and the write data have to be sent before the read command RCMD_C and the read data RDATA_C are sent in order to have correct result.
Accordingly, it is a major objective of the present invention to provide a method for scheduling execution sequence of read/write operation. It first determines whether all of the read data are completely transmitted; i.e., it determines whether there are no data to be transmitted on the bus data line. If there are no data to be transmitted on the bus data line, the write operation is activated. In addition, by suitably scheduling the sequence of the write and read operations, the address hit problem can be solved and the turn around cycles are reduced. Therefore, the read and write operations are accelerated and the executing time can be reduced.
According to the object of the invention, the invention provides a method for scheduling execution sequence of read and write operations, which is used for controlling the read and write operations between a first device and a second device. First, in step (1), whether there are read or write operations waiting to be executed between the first and the second devices is determined. If so, the method proceeds to step (2); otherwise the method ends. In step (2), it is determined whether there are more than two write operations are waiting to be executed. If so, the method proceeds to step (3); otherwise it proceeds to step (4). In step (3), it is determined whether all read operations are completed. If so, the method proceeds to step (6); otherwise it proceeds to step (4). In step (4), it is determined whether there are read operations waiting to be being executed. If so, the method proceeds to step (5); otherwise step (3) is repeated. In step (5), a determination of whether address hit occurs is made. If so, the method proceeds to step (6) and then repeats step (1). In step (6), the write operations are executed and then step (1) is repeated. An address hit mentioned above indicates that when a read operation is executed, a write operation next to the read operation corresponds to the identical data address corresponding to the read operation.
The present invention further provides a method for scheduling execution sequence of read and write operations, which is used for controlling the read and write operations between a first device and a second device. In step (1), if there is no read or write operation waiting to be executed between the first and the second devices, the method is terminated. In step (2), a plurality of read requests of the read operations and a plurality of write requests of the write operations are respectively stored into a read queue and a write queue. In step (3), the method proceeds to step (4) when there are more than two write requests in the write queue; otherwise it proceeds to step (5). In step (4), the method proceeds to step (6) when all the read operations are completed; otherwise it proceeds to step (5). In step (5), the method proceeds to step (7) when read requests are still queued in the read queue; otherwise it repeats step (4). In step (6), the write requests are popped from the write queue, and the first device executes the write operations with the second device, and step (1) is repeated. In step (7), one of the read requests is popped from the read queue when no address hit occurred, and the first device executes the read operation with the second device; otherwise step (6) is repeated. An address hit indicates that when a read operation is executed, a write operation next to the read operation corresponds to the identical data address corresponding to the read operation.